package alo.p6.work;

import alo.p6.BinaryTreeNode;

import java.util.LinkedList;
import java.util.Queue;

import static java.lang.Integer.MIN_VALUE;
//查找二叉树中的最大元素
public class FindMax {
    //递归
    int findMax(BinaryTreeNode root){
        int root_val,left,right,max=MIN_VALUE;
        if (root!=null){
            root_val=root.getData();
            left=findMax(root.getLeft());
            right=findMax(root.getRight());
//            if (right>left) max=right;
//            else max=left;
            max=Math.max(right,left);
            if (root_val>max) max=root_val;
        }
        return max;
    }
    //非递归,使用了层续遍历
    int findMax2(BinaryTreeNode root){
        BinaryTreeNode temp;
        int max=MIN_VALUE;
        Queue<BinaryTreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            temp=queue.poll();
            if (max<temp.getData()){
                max=temp.getData();
            }
            if (temp.getLeft()!=null){
                queue.offer(temp.getLeft());
            }
            if (temp.getRight()!=null){
                queue.offer(temp.getRight());
            }
        }
        return max;
    }
}
